/*
9.18 递归快速排序和非递归快速排序的优化
date:20201230 pm 23:33
更新
date:20210302 pm 00:03
完成了完美快排
1.增加了key值回插
2.增加了等值数的特殊情况的排序，以前11x1的形式会陷入死循环。
*/
#include<iostream>
#include<string>
#include<stack>
const int MAX = 1E9;
using namespace std;
void change(int& a, int& b)
{
	int k;
	k = a;
	a = b;
	b = k;
}
void print(int* A,int N)
{
	//输出数组
	for (int i = 0; i < N; i++)
	{
		cout << A[i];

	}
	cout << "\n";
}
int PartSort(int* A, int L, int R)
{
	//取本数组首个为比较值
	int key = A[L];
	int i = L + 1;
	int j = R;
	//用标杆数对这个数组划分
	while (i < j)
	{

		//从左往右的数应该比key小，指针在第一个不合理位置停下。
		while (key > A[i] && i < j)
		{
			i++;
		}
		//从右往左的数应该比key大，指针在第一个不合理位置停下。
		while (key < A[j] && j > i)
		{
			j--;
		}
		//这里实际是两种情况也可以写成一种
		if (i < j)
		{			
                //极为关键的一步，因为有可能第二个和最后一个值相等，这样会进入无限循环。必须将i推进至不等的位置。
            	while (A[i] == A[j] && i < j)
				{

					i++;
				}
			change(A[i], A[j]);
		}
	}
    //将key放到前面数组的最后一个，分的时候可以不考虑这个已排序的key了。
    change(A[L], A[i-1]);
	return i-1;
}
void QuitSort(int* A, int L, int R)
{
	if(L<R)
	{
		if (A[L] > A[R])//很重要这步
		{
			change(A[L] , A[R]);
		}
        //point就是分里的key最后的下标
		int point = PartSort(A, L, R);
        //key不参与下一趟的治了，少考虑一个元素
		QuitSort(A, L, point - 1);
		QuitSort(A, point + 1, R);
		
	}

}
void QuitSort1(int* A, stack<int>s1)
{
	while (!s1.empty())
	{
		//right left
		int R = s1.top();
		s1.pop();
		int L = s1.top();
		s1.pop();
			if (L < R)
			{
				if (A[L] > A[R])//很重要这步
				{
					change(A[L], A[R]);
				}
				int point = PartSort(A, L, R);
				//left right
				//按要求增加判断,短的子序列先排序
				if (point - 1 - L > R - point)
				{
					
					s1.push(point);
					s1.push(R);
					s1.push(L);
					s1.push(point - 1);
				}
				else
				{
					s1.push(L);
					s1.push(point - 1);
					s1.push(point);
					s1.push(R);
				}

			}
	}


}
int main()

{

	int N, M, i, j, k, l;
	cout << "排序数组大小" << endl;
	cin >> N ;
	cout << "排序数组" << endl;
	//输入N个数字 10 9 1 2 8 3 7 4 6 5 0
	int*A = new int [N];
	for (i = 0; i < N; i++)
	{
		cin>>A[i];
	}
	bool flag = 1;
	i = 0;
	j = N - 1;
	stack<int>s1;
	s1.push(i);
	s1.push(j);
	QuitSort1(A, s1);
	print(A, 10);
}